package Lee_code;

import java.util.*;
public class Lee_40 {
    List<List<Integer>> res = new ArrayList<>();
    int target_num;
    int[] candi;
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        target_num = target;
        Arrays.sort(candidates);
        candi = candidates;
        Deque<Integer> list = new ArrayDeque<>();
        dfs(list, target_num, 0);
        return res;
    }
    public void dfs(Deque<Integer> list, int rest, int start_index)
    {
        if (rest<0)
            return;
        if (rest==0) {
            res.add(new ArrayList<>(list));
            return;
        }
        for(int i=start_index; i<candi.length; i++)
        {
            if(i>start_index && candi[i]==candi[i-1])
                continue;

            list.addLast(candi[i]);
            dfs(list, rest-candi[i], i+1);
            list.removeLast();
        }
    }
}
